\section{Related Work}
\label{sec:related}

Diversification has been studied in a variety of different contexts so
we only mention some of the references here. Among them search result diversification has
arguably received the most attention (e.g.~\cite{RadlinskiBCJ09,GollapudiS09,SlivkinsRG10,SantosMO11a,SantosMO11b,SantosMO10cikm,SantosMO10www}).
In particular, Gollapudi and Sharma~\cite{GollapudiS09} adopt an
axiomatic approach and specify a set of rules that
must be adhered to in any reasonable definition of diversification
in the context of search results. A different approach is adopted by Slivkins {\it et al}~\cite{SlivkinsRG10} who employ
learning theoretic techniques for diversification of rankings. For some recent work
in diversification, the reader is referred to~\cite{SantosMO11a,SantosMO11b}.

Search diversification is different from our context in a couple of
fundamental ways. First, the primary motivation for search result diversification is keyword
disambiguation, and the intent is usually to provide the user with a
set of result webpages such that includes at least one s/he is
looking for. However, in our context, the goal is to
ensure that the user is presented with a set of items that satisfies her cumulatively. 
Second, in the search architecture, one
normally has access to all the (meta data related to) webpages stored on disk, and for
efficiency reasons, one may need to perform online/streaming decisions
on the documents, or quickly prune them to a candidate set; however,
making irrevocable online decisions is not a necessity. This
consideration makes our context a significantly harder one.

The diversification problem has also been considered extensively in the context of recommender
systems (see e.g.~\cite{YuLA09a,YuLA09b,McNeeRK06}). Several other
works on diversification have been undertaken. For example, Agrawal {\it et
al}~\cite{AgrawalGHI09} propose a maximum likelihood based
diversification objective for finding relevant documents given the
categorical information of queries and documents. Other papers on
topical diversification and information retrieval
include~\cite{ZieglerMKL05,ZhaiL06}. Vee {\it et al}~\cite{VeeSSBA08} consider
diversification for online shopping, while Drosou and Pitoura~\cite{DrosouP09,DrosouP10} have done work on diversity over
continuous data such as in the context of publish/subscribe
systems. Diversification for re-ranking documents and producing summaries has been considered by Carbonell and Goldstein~\cite{CarbonellG98}.
%Due to the vast body of work in diversification, we are only
%able to mention a handful of related work. 
We also refer the reader to the
references of these papers for further work in any specific context.

Significant algorithmic research has previously focused on {\em
  resource allocation} problems, where the goal is to allocate a set
of resources in a manner that maximizes rewards. Our algorithm also
falls in this broad framework, where we have $B$ resources in the form
of the items that we can opt to select, and the reward for a set of
selected items is given by the minimum coverage on any
feature. However, while we have a single-dimensional budget and
multi-dimensional profit, recent work on this problem (see
\cite{DevanurJSW11} and references therein) has largely focused on the
scenario where the profit function is single-dimensional but the
budgets are multi-dimensional. Another related set of resource
allocation problems that have a multi-dimensional profit function are
the {\em Santa Claus problems} (see \cite{BansalS06} and subsequent
work), where the goal is to allocate a set of items among a set of
agents so as to maximize the reward of the least satisfied
agent. However, this problem typically differs from our problem in two
ways: first, each item can be allocated to only one agent and
therefore earns rewards in only one dimension; and second, this
problem is typically considered in the offline setting where all the 
items and their valuations by the agents are known to the algorithm.
